package Fundamental.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] A1 = {4 , 6 , 1 , 8 , 3 , -1};
        int[] A2 = { 9 , 17 , 34 , 22 , 90};
        int[] merge = {4 , 6 , 1 , 8 , 3 , -1 , 9 , 17 , 34 , 22 , 90};
//        System.out.println(Arrays.toString(merge(A1 , 0 , 1 , 2 , 3)));
        System.out.println(Arrays.toString(sort(merge , 0 , merge.length-1)));
    }
    public static int[] sort(int[] array , int from , int to){
        int[] rs = null ;
        if(from == to){
            rs = new int[1];
            rs[0] = array[from];
            return rs ;
        }
        int mid = (from + to)/2;
        int[] firstHalf = sort(array, mid + 1  , to);
        int[] secordHafl = sort(array , from ,  mid);

        return merge1(firstHalf , secordHafl);
    }

    public static int[] merge( int[] array , int from1 , int to1 , int from2 , int to2){
        int[] rs = new int[to1 - from1 + to2 - from2 + 2];
        int i = from1 ;
        int j = from2 ;
        int a = 0 ;
        while(i <= to1 && j <= to2 ){
            if(array[i] <= array[j]){
                rs[a++] = array[i++];
            }else{
                rs[a++] = array[j++];
            }
        }
        while(i <= to1){
            rs[a++] = array[i++];
        }

        while(j <= to2){
            rs[a++] = array[j++];
        }
        return rs ;
    }
    public static int[] merge1( int[] A1 , int[] A2){
        int[] rs = new int[A1.length + A2.length];
        int i = 0 ;
        int j = 0 ;
        int a = 0 ;
        while(i < A1.length && j < A2.length){
           if(A1[i] <= A2[j]){
               rs[a++] = A1[i++];
           }else{
               rs[a++] = A2[j++];
           }
        }
        while(i < A1.length){
           rs[a++] = A1[i++];
        }
        while (j < A2.length){
            rs[a++] = A2[j++];
        }
        return rs ;
    }
}
